#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int pivot = 0;
        int n = nums.size();
        int begin = 0, end = n - 1;
        Sort(nums, begin, end);
    }
    void Sort(vector<int>& nums, int left, int right)
    {
        if (left >= right) return;
        int pivot = left;
        int key = nums[pivot];
        int begin = left, end = right;
        while (begin < end) {
            while (begin < end && nums[end] >= key) {
                end--;
            }
            nums[pivot] = nums[end];
            pivot = end;
            while (begin < end && nums[begin] <= key) {
                begin++;
            }
            nums[pivot] = nums[begin];
            pivot = begin;
        }
        nums[begin] = key;
        pivot = begin;
        Sort(nums, left, pivot - 1);
        Sort(nums, pivot + 1, right);

    }
};